#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    void treeToDoublyList(Node* root, Node*& prev) {
        if (root == nullptr) {
            return;
        }
        treeToDoublyList(root->left, prev);
        root->left = prev;
        if (prev) {
            prev->right = root;
        }
        prev = root;
        treeToDoublyList(root->right, prev);
    }
    Node* treeToDoublyList(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* prev = nullptr;

        treeToDoublyList(root, prev);
        Node* leftmost = root;
        Node* rightmost = root;
        while (leftmost->left) {
            leftmost = leftmost->left;
        }
        while (rightmost->right) {
            rightmost = rightmost->right;
        }
        leftmost->left = rightmost;
        rightmost->right = leftmost;
        return leftmost;
    }
};